﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace UFPE.CIn.Abc.Primality.Util
{
    public class Poly
    {
        public long[] coeficientes;

        private int grau;

        public Poly(params long[] c)
        {
            grau = c.Length-1;
            coeficientes = c;
        }

        public Poly(int grau)
        {
            this.grau = grau;
            coeficientes = new long[grau + 1];
        }

        public Poly(long grau)
        {
            this.grau = (int)grau;

            coeficientes = new long[grau + 1];
        }

        public int Grau
        {
            get
            {
                return grau;
            }
        }

        public static Poly operator *(Poly a, Poly b)
        {
            int grauA = a.Grau;
            int grauB = b.Grau;

            int grauFinal = grauA + grauB;

            Poly retorno = new Poly(grauFinal);

            for (int i = 0; i <= grauA; i++)
            {
                for (int j = 0; j <= grauB; j++)
                {
                    retorno.coeficientes[i + j] += (a.coeficientes[i] * b.coeficientes[j]);
                }
            }

            return retorno;
        }

        public static Poly operator *(Poly a, long b)
        {
            int grauA = a.Grau;

            for (int i = 0; i <= grauA; i++)
            {
                a.coeficientes[i] *= b;
            }

            return a;
        }

        public static Poly operator %(Poly a, Poly b)
        {
            int grauA = a.Grau;
            int grauB = b.Grau;
            
            // Código específico para x^r - 1
            if (grauB > 0)
            {
                if (grauA >= grauB)
                {
                    Poly ret = new Poly(grauB);

                    for (int i = grauA; i >= grauB; i--)
                    {
                        ret.coeficientes[i % grauB] += a.coeficientes[i];
                    }

                    for (int i = grauB - 1; i >= 0; i--)
                    {
                        ret.coeficientes[i] += a.coeficientes[i];
                    }

                    return CortarZeros(ret);
                }
                else
                {
                    return a;
                }
                // FIM Código específico
            }
            else
            {
                // Código geral abaixo
                int diffGraus = grauA - grauB;

                while (!(grauA < grauB || grauA == 0))
                {
                    MultiplicarOsLados(ref a, ref b, grauA, grauB);

                    long divAb = a.coeficientes[grauA] / b.coeficientes[grauB];

                    a = a.DiminuirGraus(GeracaoDeResto(a, b, grauB, diffGraus, divAb));
                    grauA = a.Grau;
                    grauB = b.Grau;
                    diffGraus = grauA - grauB;
                }

                return a;
            }
        }

        private static Poly CortarZeros(Poly a)
        {
            int cortarGraus = 0;
            int maiorGrau = a.Grau;
            while (a.coeficientes[maiorGrau--] == 0)
            {
                cortarGraus++;
            }

            Poly retorno = a.DiminuirGraus(cortarGraus);
            return retorno;
        }

        private static int GeracaoDeResto(Poly a, Poly b, int grauB, int diffGraus, long divAb)
        {
            int retorno = 0;
            bool morgar = false;
            for (int i = a.Grau, j = 0; j <= grauB; i--, j++)
            {
                a.coeficientes[i] += (-1) * (divAb * b.coeficientes[i - diffGraus]);
                if (!morgar && a.coeficientes[i] == 0)
                {
                    retorno++;
                }
                else
                {
                    morgar = true;
                }
            }
            return retorno;
        }

        private static void MultiplicarOsLados(ref Poly a, ref Poly b, int grauA, int grauB)
        {
            if ((a.coeficientes[grauA] % b.coeficientes[grauB]) != 0)
            {
                long tempAMaiorCoeficiente = a.coeficientes[grauA];
                a = a * b.coeficientes[grauB];
                b = b * tempAMaiorCoeficiente;
            }
        }

        //Transforma o coeficiente de grau mais alto em 0.
        private Poly DiminuirGraus(int numGraus)
        {
            int grau = Grau - numGraus;
            Poly clone = new Poly(grau);

            for (int i = 0; i <= grau; i++)
            {
                clone.coeficientes[i] = this.coeficientes[i];
            }

            return clone;
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            for (int i = Grau; i >=0; i--)
            {
                sb.Append(String.Format(" {0}{1}x^{2} ", (coeficientes[i] > 0 ? "+" : ""), coeficientes[i], i));
            }

            return sb.ToString();
        }

        public Poly Clone()
        {
            Poly clone = new Poly(Grau);

            for (int i = 0; i <= Grau; i++)
            {
                clone.coeficientes[i] = this.coeficientes[i];
            }

            return clone;
        }

        public static bool operator ==(Poly a, Poly b)
        {
            int grau = a.Grau;
            
            if (grau != b.Grau)
            {
                return false;
            }

            for (int i = 0; i <= grau; i++)
            {
                if (a.coeficientes[i] != b.coeficientes[i])
                {
                    return false;
                }
            }

            return true;
        }

        public static bool operator !=(Poly a, Poly b)
        {
            return !(a == b);
        }

        public override bool Equals(object obj)
        {
            return base.Equals(obj);
        }

        public override int GetHashCode()
        {
            return base.GetHashCode();
        }
    }
}